package com.liunian.algorithmstudy.tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class FindBottomLeftValue513 extends TreeNode {

	public int findBottomLeftValue1(TreeNode root) {
		Deque<TreeNode> deque = new LinkedList<>();
		deque.push(root);
		int res = 0;
		while (!deque.isEmpty()) {
			int size = deque.size();
			int temp = size;
			while (size-- > 0) {
				TreeNode treeNode = deque.pollFirst();
				if (temp - 1 == size) {
					res = treeNode.val;
				}
				if (treeNode.left != null) {
					deque.addLast(treeNode.left);
				}
				if (treeNode.right != null) {
					deque.addLast(treeNode.right);
				}
			}
		}
		return res;
	}

	private int maxDepth = 0;
	private int results = 0;
	public int findBottomLeftValue(TreeNode root) {
		int depth = root == null ? 0 : 1;
		travelsal(root, 1);
		return results;
	}

	private void travelsal(TreeNode root, int depth) {
		if (root.left == null && root.right == null) {
			if (depth > maxDepth) {
				maxDepth = depth;
				results = root.val;
			}
		}

		if (root.left != null) {
			depth++;
			travelsal(root.left, depth);
			depth--;
		}
		if (root.right != null) {
			depth++;
			travelsal(root.right, depth);
			depth--;
		}

	}


}
